package com.zrrd.zuo.stralgo;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @author ywb
 * @Description:
 * @date 2023/4/18 22:04
 */
public class PrintAllSubsquences {
    //1.一个字符串的所有子序列
    public static List<String> subs(String s){
        char[] str = s.toCharArray();
        String path = "";
        List<String> ans = new ArrayList<>();
        process1(str, 0, ans, path);
        return ans;
    }
    // str 固定参数
    // 来到了str[index]字符，index是位置
    // str[0..index-1]已经走过了！之前的决定，都在path上
    // 之前的决定已经不能改变了，就是path
    // str[index....]还能决定，之前已经确定，而后面还能自由选择的话，
    // 把所有生成的子序列，放入到ans里去
    public static void process1(char[] str,int index,List<String> ans,String path){
        if(index == str.length){
            ans.add(path);
            return;
        }
        //不要index位置的值
        process1(str,index + 1,ans,path);
        //要index的值
        process1(str,index + 1,ans,path + str[index]);
    }
    //去重的子序列
    public static List<String> subsNoReplace(String s){
        char[] str = s.toCharArray();
        String path = "";
        List<String> ans = new ArrayList<>();
        HashSet<String> set = new HashSet<>();
        process2(str, 0, set, path);
        for (String s1 : set) {
            ans.add(s1);
        }
        return ans;
    }
    public static void process2(char[] str,int index,HashSet<String> set,String path){
        if(index == str.length){
            set.add(path);
            return;
        }
        //不要index位置的值
        process2(str,index + 1,set,path);
        //要index的值
        process2(str,index + 1,set,path + str[index]);
    }
    public static void main(String[] args) {
        String s = "aa";
        //List<String> subs = subs(s);
        List<String> subs = subsNoReplace(s);
        for (String sub : subs) {
            System.out.println(sub);
        }
    }
}
